package backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 和为n 全部组合 可以被无限次选取
 */
public class AssemblySum2 {

    public static void main(String[] args) {
        int[] candidates = new int[] {2,3,6,7};
        int target = 7;

        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates,target,0,new ArrayList<>(),result);
        System.out.println(result);
    }

    private static void backtrack(int[] candidates, int target, int startIndex, List<Integer> path,List<List<Integer>> result) {
        Integer sum = path.stream().reduce(Integer::sum).orElse(0);
        if (sum.equals(target)) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 总和比目标大 结束递归
        if (sum > target) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtrack(candidates, target, i, path, result);
            path.remove(path.size() - 1);
        }
    }
}
